Companies use database systems to store and search data used in various aspects of their businesses. The data may include as many as several million records, at least some of which the companies wish to keep private, such as, for example, customer information. Such information may be of value to others who may have a malicious intent. If a company's adversary was able to obtain such private information, the adversary could create problems for the company, its customers, or both.
One common method used to protect valuable information in a database and to comply with privacy regulations or policies is encryption. However, use of encrypted data in a database raises other issues, such as, for example, how to permit authorized access to the data by existing applications and how to find particular items of the data without decrypting all of the data and performing a linear search.
Existing database systems solved the above-mentioned problems by using what can be called deterministic encryption. In such database systems, an item of plaintext will always be encrypted to the same ciphertext when using the same encryption key. Examples of deterministic encryption include use of block ciphers in electronic codebook (ECB) mode or use of a constant initialization vector (IV). Because deterministic encryption always encrypts the same plaintext to the same ciphertext when using a given cryptographic key, data patterns may be recognizable, resulting in information leakage. This is especially a problem when data to be encrypted is too large to fit into a single block, which may be 8 or 16 bytes in length, depending on which block cipher algorithm is used.